package com.njupt.DynamicProgramming;

import com.njupt.Tree.TreeNode;
import org.aspectj.weaver.Dump;

import java.util.*;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/19 22:22
 * @Description: 337. 打家劫舍 III 树形问题
 * @Version: 1.0
 */


public class Rob3_337 {

    public int rob(TreeNode root) {
//        int[] result = robTree(root);
//        return Math.max(result[0], result[1]);
        Map<TreeNode, Integer> map = new HashMap<>();
        return robTree2(root,map);
    }

    /**
     * 动态规划法
     * @param root
     * @return
     */
    private int[] robTree(TreeNode root) {

        int[] res = new int[2];
        if(root == null){
            return res;
        }
        int[] leftDp = robTree(root.left);
        int[] rightDp = robTree(root.right);

        //偷当前节点
        res[1] = root.val + leftDp[0] + rightDp[0];
        //不偷当前节点
        res[0] = Math.max(leftDp[0],leftDp[1]) + Math.max(rightDp[0],rightDp[1]);
        return res;
    }


    /**
     * 暴力法
     * @param root
     * @return
     */
    private int robTree1(TreeNode root) {
        if(root == null){
            return 0;
        }

        //这行代码可有可无，没有的话递归就会深入一层，有的话递归就会少一层
        if(root.left == null && root.right == null){
            return root.val;
        }

        //偷父亲节点
        int val1 = root.val;
        if(root.left != null){
            val1 += robTree1(root.left.left) + robTree1(root.left.right);
        }
        if(root.right != null){
            val1 += robTree1(root.right.left) + robTree1(root.right.right);
        }

        //不偷父亲节点
        int val2 = robTree1(root.left) + robTree1(root.right);
        return Math.max(val1,val2);

    }

    /**
     * 由于递归时这里有重复计算，所以可以使用带备忘录的递归
     * @param root
     * @return
     */
    private int robTree2(TreeNode root, Map<TreeNode, Integer> map) {
        if(root == null){
            return 0;
        }

        //这行代码可有可无，没有的话递归就会深入一层，有的话递归就会少一层
        if(root.left == null && root.right == null){
            return root.val;
        }
        if(map.containsKey(root)){
            return map.get(root);
        }

        //偷父亲节点
        int val1 = root.val;
        if(root.left != null){
            val1 += robTree2(root.left.left,map) + robTree2(root.left.right,map);
        }
        if(root.right != null){
            val1 += robTree2(root.right.left,map) + robTree2(root.right.right,map);
        }

        //不偷父亲节点
        int val2 = robTree2(root.left,map) + robTree2(root.right,map);
        map.put(root,Math.max(val1,val2));
        return Math.max(val1,val2);

    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(1);

        Rob3_337 test = new Rob3_337();
        System.out.println(test.rob(root));
    }
}
